/**
 * 二叉树节点定义
 */
export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}

/**
 * 将二叉树展开为链表（原地修改）
 * 按照前序遍历的顺序，将二叉树展开为一个只有右子树的链表
 * 
 * 算法思路（迭代法，使用栈）：
 * 1. 使用栈进行前序遍历（根 -> 左 -> 右）
 * 2. 使用 prev 指针记录前一个访问的节点
 * 3. 对于每个节点：
 *    - 将左子树置为 null
 *    - 将前一个节点的右子树指向当前节点
 *    - 更新 prev 为当前节点
 * 4. 按照前序遍历的顺序处理节点，最终形成只有右子树的链表
 * 
 * 注意：由于栈是后进先出（LIFO），所以先入栈右子树，再入栈左子树，
 *       这样出栈时就是：根 -> 左 -> 右 的前序遍历顺序
 * 
 * 时间复杂度：O(n)，其中 n 是树中节点的数量
 * 空间复杂度：O(n)，最坏情况下栈需要存储所有节点
 * 
 * @param root 二叉树的根节点（会被原地修改）
 */
function flatten(root: TreeNode | null): void {
    // 空树直接返回
    if (!root) return;
    
    // 使用栈进行前序遍历，初始时将根节点入栈
    let stack: TreeNode[] = [root];
    
    // 记录前一个访问的节点，用于连接链表
    let prev: TreeNode | null = null;
    
    // 当栈不为空时，继续遍历
    while (stack.length) {
        // 从栈顶取出一个节点（后进先出）
        let node = stack.pop() as TreeNode;
        
        // 先将右子树入栈（后处理）
        if (node.right) stack.push(node.right);
        
        // 再将左子树入栈（先处理）
        // 注意：由于栈是 LIFO，先入右后入左，出栈时就是：根 -> 左 -> 右 的顺序
        if (node.left) stack.push(node.left);
        
        // 将当前节点的左子树置为 null（展开为链表后不需要左子树）
        node.left = null;
        
        // 如果存在前一个节点，将前一个节点的右子树指向当前节点
        // 这样就形成了链表的连接
        if (prev) {
            prev.right = node;
        }
        
        // 更新 prev 为当前节点，用于下一次连接
        prev = node;
    }
};